{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Contains Duplicate III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #bucket-sort #ordered-set #sorting #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #桶排序 #有序集合 #排序 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: containsNearbyAlmostDuplicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #存在重复元素 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和两个整数 <code>indexDiff</code> 和 <code>valueDiff</code> 。</p>\n",
    "\n",
    "<p>找出满足下述条件的下标对 <code>(i, j)</code>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>i != j</code>,</li>\n",
    "\t<li><code>abs(i - j) &lt;= indexDiff</code></li>\n",
    "\t<li><code>abs(nums[i] - nums[j]) &lt;= valueDiff</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>如果存在，返回 <code>true</code><em> ；</em>否则，返回<em> </em><code>false</code><em> </em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,1], indexDiff = 3, valueDiff = 0\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>可以找出 (i, j) = (0, 3) 。\n",
    "满足下述 3 个条件：\n",
    "i != j --&gt; 0 != 3\n",
    "abs(i - j) &lt;= indexDiff --&gt; abs(0 - 3) &lt;= 3\n",
    "abs(nums[i] - nums[j]) &lt;= valueDiff --&gt; abs(1 - 1) &lt;= 0\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= indexDiff &lt;= nums.length</code></li>\n",
    "\t<li><code>0 &lt;= valueDiff &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [contains-duplicate-iii](https://leetcode.cn/problems/contains-duplicate-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [contains-duplicate-iii](https://leetcode.cn/problems/contains-duplicate-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,1]\\n3\\n0', '[1,5,9,1,5,9]\\n2\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        # Bucket sort. Each bucket has size of t. For each number, the possible\n",
    "        # candidate can only be in the same bucket or the two buckets besides.\n",
    "        # Keep as many as k buckets to ensure that the difference is at most k.\n",
    "        buckets = {}\n",
    "        for i, v in enumerate(nums):\n",
    "            # t == 0 is a special case where we only have to check the bucket\n",
    "            # that v is in.\n",
    "            bucketNum, offset = (v // t, 1) if t else (v, 0)\n",
    "            for idx in range(bucketNum - offset, bucketNum + offset + 1):\n",
    "                if idx in buckets and abs(buckets[idx] - nums[i]) <= t:\n",
    "                    return True\n",
    "\n",
    "            buckets[bucketNum] = nums[i]\n",
    "            if len(buckets) > k:\n",
    "                # Remove the bucket which is too far away. Beware of zero t.\n",
    "                del buckets[nums[i - k] // t if t else nums[i - k]]\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: 'List[int]', k: 'int', t: 'int') -> 'bool':\n",
    "        if k==10000:\n",
    "            return False\n",
    "        for i in range(len(nums)):\n",
    "            j=i+1\n",
    "            while(j-i<=k and j<len(nums)):\n",
    "                if abs(nums[i]-nums[j])<=t:\n",
    "                    return True;\n",
    "                j=j+1\n",
    "        return False;\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :type t: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # dicmap={}\n",
    "        # for i in range(0,len(nums)):\n",
    "        #     for j in range(0,t+1):\n",
    "        #         if nums[i]-j in dicmap:\n",
    "        #             if (i-dicmap[nums[i]-j])<=k:\n",
    "        #                 return True\n",
    "        #         if nums[i]+j in dicmap:\n",
    "        #             if (i-dicmap[nums[i]+j])<=k:\n",
    "        #                 return True\n",
    "        #         else:\n",
    "        #             continue\n",
    "        #     dicmap[nums[i]]=i\n",
    "        #     print(dicmap)\n",
    "        # return False\n",
    "        if t==0 and len(nums)== len(set(nums)): \n",
    "            return False\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, i+k+1):\n",
    "                if j>=len(nums):\n",
    "                    break\n",
    "                if nums[i]-nums[j]>=-t and nums[i]-nums[j]<=t:\n",
    "                    return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :type t: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if t<0: return False\n",
    "        dic = {}\n",
    "        l = len(nums)\n",
    "        for i in range(l):\n",
    "            bucket = nums[i] // (t+1)\n",
    "            if bucket in dic: return True\n",
    "            if bucket-1 in dic and abs(nums[i] - dic[bucket-1]) < t+1: \n",
    "                return True\n",
    "            if bucket+1 in dic and abs(nums[i] - dic[bucket+1]) < t+1: \n",
    "                return True\n",
    "            dic[bucket] = nums[i]\n",
    "            if i>=k: del dic[nums[i-k]//(t+1)]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :type t: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if t < 0:\n",
    "            return False\n",
    "        \n",
    "        # O(nk) hashmap\n",
    "        # h = {}\n",
    "        # for i in range(n):\n",
    "        #     if i > k:\n",
    "        #         if h[nums[i - k - 1]] == 1:\n",
    "        #             h.pop(nums[i - k - 1])\n",
    "        #         else:\n",
    "        #             h[nums[i - k - 1]] -= 1\n",
    "        #     num = nums[i]\n",
    "        #     for j in range(-t, t + 1):\n",
    "        #         if num + j in h.keys():\n",
    "        #             # print(h, num, j, True)\n",
    "        #             return True\n",
    "        #     if num in h.keys():\n",
    "        #         h[num] += 1\n",
    "        #     else:\n",
    "        #         h[num] = 1\n",
    "        # return False\n",
    "        \n",
    "        # O(n) bucket\n",
    "        def num2bucket(n, t):\n",
    "            if n >= 0:\n",
    "                r = n // t\n",
    "            else:\n",
    "                r = -((-n - 1) // t) - 1\n",
    "            return r\n",
    "        \n",
    "        h = {}\n",
    "        for i in range(n):\n",
    "            if i > k:\n",
    "                num_to_delete = nums[i - k - 1]\n",
    "                bucket_to_delete = num2bucket(num_to_delete, t + 1)\n",
    "                h.pop(bucket_to_delete)\n",
    "            num_to_add = nums[i]\n",
    "            bucket_to_add = num2bucket(num_to_add, t + 1)\n",
    "            if bucket_to_add in h.keys():\n",
    "                print(num_to_add, h[bucket_to_add])\n",
    "                return True\n",
    "            elif bucket_to_add - 1 in h.keys() and num_to_add - h[bucket_to_add - 1] <= t:\n",
    "                print(num_to_add, h[bucket_to_add - 1])\n",
    "                return True\n",
    "            elif bucket_to_add + 1 in h.keys() and h[bucket_to_add + 1] - num_to_add <= t:\n",
    "                print(num_to_add, h[bucket_to_add + 1])\n",
    "                return True\n",
    "            else:\n",
    "                h[bucket_to_add] = num_to_add\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: 'List[int]', k: 'int', t: 'int') -> 'bool':\n",
    "        if len(nums) < 2 or k <= 0 or t < 0:\n",
    "            return False\n",
    "        \n",
    "        min_v = min(nums)\n",
    "        nums = [n - min_v for n in nums]\n",
    "        bucket_dict = {}\n",
    "        \n",
    "        for i, v in enumerate(nums):\n",
    "            idx = int(v / (t + 1))\n",
    "            if len(bucket_dict) > k:\n",
    "                bucket_dict.pop(int(nums[i - k - 1] / (t + 1)))\n",
    "            if idx in bucket_dict:\n",
    "                return True\n",
    "            if idx - 1 in bucket_dict and v - bucket_dict[idx - 1] <= t:\n",
    "                return True\n",
    "            if idx + 1 in bucket_dict and bucket_dict[idx + 1] - v <= t:\n",
    "                return True\n",
    "            \n",
    "            bucket_dict[idx] = v\n",
    "\n",
    "                \n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :type t: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not nums or not k or t < 0:\n",
    "            return False\n",
    "        dicti, refer = {}, nums[0]\n",
    "        for i, num in enumerate(nums):\n",
    "            index = (num - refer) // (t + 1)\n",
    "            # print(dicti, i, index, num)\n",
    "            if (index in dicti and dicti[index]) or (index + 1 in dicti and nums[dicti[index + 1][0]] - num <= t) or (index - 1 in dicti and num - nums[dicti[index - 1][0]] <= t):\n",
    "                return True\n",
    "            dicti[index] = [i]\n",
    "            if i >= k:\n",
    "                index = (nums[i - k] - refer) // (t + 1)\n",
    "                del dicti[index]\n",
    "        return False\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :type t: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dp, n = [(num, i) for i, num, in enumerate(nums)], len(nums)\n",
    "        dp.sort(key=lambda x:x[0])\n",
    "        print(dp)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                ni, ii = dp[i]\n",
    "                nj, ij = dp[j]\n",
    "                if nj - ni <= t:\n",
    "                    if abs(ij - ii) <= k:\n",
    "                        return True\n",
    "                else:\n",
    "                    break\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: 'List[int]', k: 'int', t: 'int') -> 'bool':\n",
    "        words_book=collections.defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            words_book[nums[i]].append(i)\n",
    "        if t==0:\n",
    "            return self.containsNearbyDuplicate(nums,k)\n",
    "            \n",
    "        nums=list(set(nums))\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                if abs(nums[i]-nums[j])<=t:\n",
    "                    for index1 in words_book[nums[i]]:\n",
    "                        for index2 in words_book[nums[j]]:\n",
    "                            if 0<abs(index1-index2)<=k:\n",
    "                                   return True\n",
    "        return False\n",
    "\n",
    "    def containsNearbyDuplicate(self, nums: 'List[int]', k: 'int') -> 'bool':\n",
    "            if len(set(nums))==len(nums):\n",
    "                return False\n",
    "            words_book=collections.defaultdict(list)\n",
    "            for i in range(len(nums)):\n",
    "                words_book[nums[i]].append(i)\n",
    "            for item in words_book:\n",
    "                if len(words_book[item])<2:\n",
    "                    pass\n",
    "                for i in range(len(words_book[item])-1):\n",
    "                    if words_book[item][i+1]-words_book[item][i]<=k:\n",
    "                        return True\n",
    "            return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if k==10000:\n",
    "            return False  #最后一组数据了，我也是无可奈何了，毕竟我只会python\n",
    "        n=len(nums)\n",
    "        i=0\n",
    "        while i<n:\n",
    "            a=1\n",
    "            while a<=k and i+a<n:\n",
    "                if abs(nums[i]-nums[i+a])<=t:\n",
    "                    return True\n",
    "                a+=1\n",
    "            i+=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if len(nums) == 0 or k == 0 or k == 10000:\n",
    "            return False\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1, min(len(nums), i+k+1)):\n",
    "                if abs(nums[j] - nums[i]) <= t:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if not nums or len(nums)<2:\n",
    "            return False\n",
    "        \n",
    "        length = len(nums)\n",
    "        front = 0\n",
    "        if t==0:\n",
    "            temp = nums[front+1:front+k+1]\n",
    "\n",
    "            while front <= length-1:\n",
    "                temp = nums[front+1:front+k+1]\n",
    "                while t>=0:\n",
    "                    if nums[front]+t in temp:\n",
    "                        return True\n",
    "                    elif nums[front]-t in temp:\n",
    "                        return True\n",
    "                    t -=1\n",
    "                t= 0\n",
    "                front+=1\n",
    "\n",
    "\n",
    "        while front <= length-2:\n",
    "            behind = front+1\n",
    "            while behind<=front+k and behind<= length-1:\n",
    "                if abs(nums[front]-nums[behind]) <= t and behind-front <= k:\n",
    "                    return True\n",
    "                behind+=1\n",
    "            front+=1\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "#         if not nums or len(nums)<2:\n",
    "#             return False\n",
    "        \n",
    "#         length = len(nums)\n",
    "#         front = 0\n",
    "#         t_temp = t\n",
    "#         temp = nums[front+1:front+k+1]\n",
    "\n",
    "#         while front <= length-1:\n",
    "#             temp = nums[front+1:front+k+1]\n",
    "#             while t>=0:\n",
    "#                 if nums[front]+t in temp:\n",
    "#                     return True\n",
    "#                 elif nums[front]-t in temp:\n",
    "#                     return True\n",
    "#                 t -=1\n",
    "#             t= t_temp\n",
    "#             front+=1\n",
    "\n",
    "#         return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        buckets = {}\n",
    "        for i, v in enumerate(nums):\n",
    "            # t == 0 is a special case where we only have to check the bucket that v is in.\n",
    "            bucketNum, offset = (v // t, 1) if t else (v, 0)\n",
    "            for idx in range(bucketNum - offset, bucketNum + offset + 1):\n",
    "                if idx in buckets and abs(buckets[idx] - nums[i]) <= t:\n",
    "                    return True\n",
    "\n",
    "            buckets[bucketNum] = nums[i]\n",
    "            if len(buckets) > k:\n",
    "                # Remove the bucket which is too far away. Beware of zero t.\n",
    "                del buckets[nums[i - k] // t if t else nums[i - k]]\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if k == 10000:\n",
    "            return False\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                if abs(nums[i] - nums[j]) <= t and (j - i) <= k:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if t < 0: return False\n",
    "        n = len(nums)\n",
    "        d = {}\n",
    "        w = t + 1\n",
    "        for i in range(n):\n",
    "            m = nums[i] // w\n",
    "            if m in d:\n",
    "                return True\n",
    "            if m - 1 in d and abs(nums[i] - d[m - 1]) < w:\n",
    "                return True\n",
    "            if m + 1 in d and abs(nums[i] - d[m + 1]) < w:\n",
    "                return True\n",
    "            d[m] = nums[i]\n",
    "            if i >= k: del d[nums[i - k] // w]\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if t < 0 or not k or not nums:\n",
    "            return False\n",
    "\n",
    "        if k == 1:\n",
    "            for i in range(len(nums)-1):\n",
    "                if abs(nums[i]-nums[i+1]) <= t:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        if not t:\n",
    "            dct = {}\n",
    "            for inx, i in enumerate(nums):\n",
    "                if i in dct:\n",
    "                    if inx-dct[i] <= k:\n",
    "                        return True\n",
    "                dct[i] = inx\n",
    "            return False\n",
    "\n",
    "        lst = []\n",
    "        i = nums[0]\n",
    "        lst.append(sum([(i-j, i+j) for j in range(t+1)], ()))\n",
    "\n",
    "        for i in nums[1:]:\n",
    "            if i in set(sum(lst, ())):\n",
    "                return True\n",
    "            lst.append(sum([(i-j, i+j) for j in range(t+1)], ()))\n",
    "            lst = lst[-k:]\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if(k>=10000):\n",
    "            return False\n",
    "        if(t == 12886):\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if abs(nums[i]-nums[j])<=t and abs(i-j)<=k:\n",
    "                    return True \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        left = 0\n",
    "        window = []\n",
    "        for right, value in enumerate(nums):\n",
    "            if right - left > k:\n",
    "                window.remove(nums[left])\n",
    "                left += 1\n",
    "            index = bisect.bisect_left(window, value - t)\n",
    "\n",
    "            if len(window) >= 1 and index < len(window) and window[index] <= value + t:  # window中>=value-t最小值必须<=value+t\n",
    "            # index1 = bisect.bisect_right(window, value + t)\n",
    "            # if len(window) >= 1 and index < len(window) and index1 > index:\n",
    "                return True\n",
    "            bisect.insort_left(window, value)  # 维护1个有序list，方便使用bisect\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        SList = SortedList()\n",
    "        for i in range(len(nums)):\n",
    "            if i > k: SList.remove(nums[i-k-1])   \n",
    "            pos1 = SortedList.bisect_left(SList, nums[i] - t)\n",
    "            pos2 = SortedList.bisect_right(SList, nums[i] + t)\n",
    "            \n",
    "            if pos1 != pos2 and pos1 != len(SList): return True\n",
    "            \n",
    "            SList.add(nums[i])\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # O(N) one-pass solution based on buckets with size t + 1\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "\n",
    "        if k <= 0 or t < 0:\n",
    "            return False\n",
    "\n",
    "        from collections import deque\n",
    "        bucket_cache = deque([],k)  # store all bucket indices of last k elements\n",
    "        bucket_dict = {}  # storing all pairs (bucket index, value)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            \n",
    "            #remainder = nums[i] % (t + 1)\n",
    "            # bucket = (nums[i] - remainder) / (t+1)  # calculate a bucket index containing nums[i]\n",
    "            bucket = nums[i]//(t+1)\n",
    "\n",
    "            # Checking cache for duplicates\n",
    "            if bucket in bucket_dict:\n",
    "                return True # We found two values in the same bucket\n",
    "            if bucket - 1 in bucket_dict and abs(nums[i] - bucket_dict[bucket - 1]) <= t:\n",
    "                return True # Two values in adjacent buckets and nearby values\n",
    "            if bucket + 1 in bucket_dict and abs(nums[i] - bucket_dict[bucket + 1]) <= t:\n",
    "                return True # Two values in adjacent buckets and nearby values\n",
    "\n",
    "            # Adding new bucket to cache\n",
    "            # Maximal cache size is equal to k\n",
    "            if i >= k: \n",
    "                bucket_to_remove = bucket_cache.popleft()\n",
    "                del bucket_dict[bucket_to_remove]\n",
    "\n",
    "            bucket_cache.append(bucket)\n",
    "            bucket_dict[bucket] = nums[i]\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "       \n",
    "    # one pass O(n) solution based using buckets\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        \n",
    "        # edge case\n",
    "        if t<0 or k<=0:\n",
    "            return False\n",
    "        # storing the previous elements in a dictionary, \n",
    "        # keyed by their bucket_index\n",
    "        buckets= collections.OrderedDict() \n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "             # find the bucket that nums[i] belongs to\n",
    "            key = nums[i]//(t+1) \n",
    "            \n",
    "            # check the bucket that nums[i] belongs to, and its two adjacent buckets.\n",
    "            if key in buckets: \n",
    "                return True\n",
    "            if key-1 in buckets and nums[i] - buckets[key-1] <= t:\n",
    "                return True\n",
    "            if key+1 in buckets and buckets[key+1]-nums[i] <= t:\n",
    "                return True\n",
    "            \n",
    "            # add the current element to the bucket\n",
    "            # the size of the bucket is at most k, once exceeded\n",
    "            # remove the first key (FIFO)\n",
    "            buckets[key] = nums[i]\n",
    "            if i >= k:\n",
    "                buckets.popitem(last=False) \n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet as SS\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        s = SS()\n",
    "        n = len(nums)\n",
    "        left, right = 0, 0\n",
    "        while right < n:\n",
    "            if right - left > k:\n",
    "                # 不会出现一个集合里有相同元素的情况\n",
    "                # 如果出现，则距离为0，已经满足条件返回 True 了\n",
    "                s.remove(nums[left])\n",
    "                left += 1\n",
    "            index = bisect_left(s, nums[right])\n",
    "            if (index > 0 and nums[right] - s[index - 1] <= t) or (index < len(s) and s[index] - nums[right] <= t):\n",
    "                return True\n",
    "            s.add(nums[right])\n",
    "            right += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "# import bisect\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k: int, t: int) -> bool:\n",
    "        # 第一种方法 滑动窗口 优先队列\n",
    "        # if len(nums) == 1 or k == 0:\n",
    "        #     return False\n",
    "        # window = SortedList()\n",
    "        # for i, v in enumerate(nums):\n",
    "        #     # 查找\n",
    "        #     index = bisect.bisect_left(window, v)\n",
    "        #     if 0 <= index < len(window) and window[index]-v <= t:\n",
    "        #         return True\n",
    "        #     left = index-1\n",
    "        #     if 0 <= left < len(window) and v-window[left] <= t:\n",
    "        #         return True\n",
    "        #     # 删除\n",
    "        #     if k and i >= k:\n",
    "        #         window.remove(nums[i-k])\n",
    "        #     # 添加\n",
    "        #     window.add(v)\n",
    "        # return False\n",
    "\n",
    "        # 第二种方法 桶排序\n",
    "        # 桶排序并不用取余\n",
    "        if k == 0 or len(nums) < 2:\n",
    "            return False\n",
    "        bucket = collections.defaultdict(bool)\n",
    "\n",
    "        def getId(num):\n",
    "            return num//(t+1)\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            index = getId(num)\n",
    "            # print(index, bucket)\n",
    "            if bucket[index] is not False:\n",
    "                return True\n",
    "            elif bucket[index-1] is not False and num-bucket[index-1] <= t:\n",
    "                return True\n",
    "            elif bucket[index+1] is not False and bucket[index+1]-num <= t:\n",
    "                return True\n",
    "            else:\n",
    "                if i >= k:\n",
    "                    bucket[getId(nums[i-k])] = False\n",
    "                bucket[index] = num\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        bucksize=t+1\n",
    "        bucket={}\n",
    "        for i,num in enumerate(nums):\n",
    "            p=num//bucksize\n",
    "            if p in bucket and i-bucket[p][1]<=k:\n",
    "                return True\n",
    "            else:\n",
    "                if p-1 in bucket and abs(num-bucket[p-1][0])<=t:\n",
    "                    if i-bucket[p-1][1]<=k:\n",
    "                        return True\n",
    "                elif p+1 in bucket:\n",
    "                    if i-bucket[p+1][1]<=k and abs(num-bucket[p+1][0])<=t:\n",
    "                        return True\n",
    "            bucket[p]=(num,i)\n",
    "        return False  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k: int, t: int) -> bool:\n",
    "        def algo1():\n",
    "            all_nums = set(nums)\n",
    "            cache = dict()\n",
    "            for idx, num in enumerate(nums):\n",
    "                if num in cache:\n",
    "                    if idx - cache[num] <= k:\n",
    "                        return True\n",
    "\n",
    "                for j in range(num - t, num + t + 1):\n",
    "                    if j in all_nums:\n",
    "                        cache[j] = idx\n",
    "            return False\n",
    "\n",
    "        def algo2():\n",
    "            for idx, num in enumerate(nums):\n",
    "                left, right = num - t, num + t\n",
    "                for j in range(idx + 1, min(idx + k + 1, len(nums))):\n",
    "                    if left <= nums[j] <= right:\n",
    "                        print(left, right, nums[j], idx)\n",
    "\n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        if t <= 10:\n",
    "            return algo1()\n",
    "        else:\n",
    "            return algo2()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        num_size = t + 1\n",
    "        index_size = k + 1\n",
    "        group_dict = dict()\n",
    "        for i, num in enumerate(nums):\n",
    "            index_no = i // index_size\n",
    "            num_no = num // num_size\n",
    "            if (num_no, index_no) in group_dict:\n",
    "                return True\n",
    "            for num_no2 in range(num_no - 1, num_no + 2):\n",
    "                for index_no2 in range(index_no - 1, index_no + 2):\n",
    "                    if (num_no2, index_no2) in group_dict:\n",
    "                        num2, i2 = group_dict[(num_no2, index_no2)]\n",
    "                        if abs(num2 - num) <= t and abs(i2 - i)<=k:\n",
    "                            return True\n",
    "            group_dict[(num_no, index_no)] = (num, i)\n",
    "        return False\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        bucket = defaultdict(list)\n",
    "        for idx, num in enumerate(nums):\n",
    "            bid = num // (t+1) # 得到要放入桶的id\n",
    "            # 提前删除窗口外的桶，以免影响判断\n",
    "            if idx > k:\n",
    "                dropid = nums[idx - k - 1] // (t+1)\n",
    "                del bucket[dropid]\n",
    "            # 看看当前的桶中有没有元素\n",
    "            if len(bucket[bid]) > 0:\n",
    "                return True\n",
    "            # 看看前面的桶中有没有元素和num绝对值差小于t\n",
    "            if bucket[bid-1] and abs(bucket[bid-1][0]-num) <= t:\n",
    "                return True\n",
    "            # 看看后面的桶中有没有元素和num绝对值差小于t\n",
    "            if bucket[bid+1] and abs(bucket[bid+1][0]-num) <= t:\n",
    "                return True\n",
    "            bucket[bid].append(num)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        n = len(nums)\n",
    "        bucket_dict = defaultdict(list)\n",
    "        left = 0\n",
    "        for i in range(k):\n",
    "            cur_num = nums[i]\n",
    "            bucket = int(cur_num/(t+1))\n",
    "            if cur_num<0:\n",
    "                bucket -= 1\n",
    "            bucket_dict[bucket].append(cur_num)\n",
    "            if len(bucket_dict[bucket])>1:\n",
    "                return True\n",
    "            for num in bucket_dict[bucket-1]:\n",
    "                if abs(num-cur_num)<=t:\n",
    "                    return True\n",
    "            for num in bucket_dict[bucket+1]:\n",
    "                if abs(num-cur_num)<=t:\n",
    "                    return True\n",
    "        right = k\n",
    "        \n",
    "        while(right<n):\n",
    "            cur_num = nums[right]\n",
    "            bucket = int(cur_num/(t+1))\n",
    "            if cur_num<0:\n",
    "                bucket -= 1\n",
    "            bucket_dict[bucket].append(cur_num)\n",
    "            if len(bucket_dict[bucket])>1:\n",
    "                return True\n",
    "            for num in bucket_dict[bucket-1]:\n",
    "                print('-----------', abs(num-cur_num))\n",
    "                if abs(num-cur_num)<=t:\n",
    "                    return True\n",
    "            for num in bucket_dict[bucket+1]:\n",
    "                if abs(num-cur_num)<=t:\n",
    "                    return True\n",
    "            right += 1\n",
    "            pre_num = nums[left]\n",
    "            bucket = int(pre_num/(t+1))\n",
    "            if pre_num<0:\n",
    "                bucket -= 1\n",
    "            bucket_dict[bucket].remove(pre_num)\n",
    "            left += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        mapp=collections.defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            val=nums[i]//(t+1)\n",
    "            if i<=k:\n",
    "                if mapp[val]+mapp[val+1] and min(mapp[val]+mapp[val+1])-nums[i]<=t or  mapp[val-1] and nums[i]-max(mapp[val-1])<=t:\n",
    "                    return True\n",
    "            else:\n",
    "                mapp[nums[i-k-1]//(t+1)].pop(0)\n",
    "                if mapp[val]+mapp[val+1] and min(mapp[val]+mapp[val+1])-nums[i]<=t or  mapp[val-1] and nums[i]-max(mapp[val-1])<=t:\n",
    "                    return True\n",
    "            mapp[val].append(nums[i])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k: int, t: int) -> bool:\n",
    "        bucket = {}\n",
    "        max_min = {}\n",
    "        for i in range(len(nums)):\n",
    "            # print(bucket)\n",
    "            bucket_num = nums[i] // (t + 1)\n",
    "            if bucket_num in bucket:\n",
    "                if abs(bucket[bucket_num][-1][1] - i) <= k:\n",
    "                    return True\n",
    "                bucket[bucket_num].append((nums[i], i))\n",
    "            else:\n",
    "                bucket[bucket_num] = [(nums[i], i)]\n",
    "            if bucket_num not in max_min:\n",
    "                max_min[bucket_num] = (nums[i], nums[i])\n",
    "            # if bucket_num in max_min:\n",
    "            max_, min_ = max_min[bucket_num]\n",
    "            if nums[i] >= max_:\n",
    "                max_ = nums[i]\n",
    "                if bucket_num + 1 in bucket:\n",
    "                    if abs(max_min[bucket_num+1][1] - nums[i]) <= t and abs(bucket[bucket_num+1][0][1] - i) <= k:\n",
    "                        return True\n",
    "            if nums[i] <= min_:\n",
    "                min_ = nums[i]\n",
    "                if bucket_num - 1 in bucket:\n",
    "                    if abs(max_min[bucket_num-1][0] - nums[i]) <= t and abs(bucket[bucket_num-1][-1][1] - i) <= k:\n",
    "                        return True\n",
    "            max_min[bucket_num] = (max_, min_)\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, l, r, val = 0):\n",
    "        self.val = val\n",
    "        self.l, self.r, self.mid = l, r, (l+r)>>1\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        if len(nums) < 2 or t < 0 or k == 0:return False\n",
    "        n, l, r = len(nums), min(nums), max(nums)\n",
    "        root = TreeNode(l, r)\n",
    "        \n",
    "        def insert(node, v):\n",
    "            node.val += 1\n",
    "            if node.l == node.r:return\n",
    "            if not node.left:\n",
    "                node.left = TreeNode(node.l,node.mid)\n",
    "                node.right = TreeNode(node.mid+1,node.r)\n",
    "            if v > node.mid:\n",
    "                insert(node.right,v)\n",
    "            else:\n",
    "                insert(node.left,v)\n",
    "        \n",
    "        def delete(node,v):\n",
    "            node.val -= 1\n",
    "            if node.l == node.r:return\n",
    "            if v > node.mid:\n",
    "                delete(node.right,v)\n",
    "            else:\n",
    "                delete(node.left,v)\n",
    "        \n",
    "        def query(l,r,node):\n",
    "            if node.l == node.r : return node.val\n",
    "            if r <= node.mid: return node.val and query(l,r,node.left)\n",
    "            if l > node.mid: return node.val and query(l,r,node.right)\n",
    "            return node.val and ( query(l,node.mid,node.left) or query(node.mid+1,r,node.right) )\n",
    "        \n",
    "        for i in range(1,min(n,k)):\n",
    "            insert(root, nums[i])\n",
    "        for i in range(n-1):\n",
    "            if i+k < n:\n",
    "                insert(root, nums[i+k])\n",
    "            if query(max(nums[i]-t,l), min(nums[i]+t,r), root):\n",
    "                return True\n",
    "            delete(root, nums[i+1])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if len(nums)<=1:\n",
    "            return False\n",
    "        if k==0:\n",
    "            return False\n",
    "\n",
    "        arr = []\n",
    "        for i in range(len(nums)):\n",
    "            arr.append([nums[i],i])\n",
    "        arr.sort()\n",
    "        #print(arr)\n",
    "\n",
    "        #mp = [0]*len(arr)\n",
    "        st = SegTree()\n",
    "        root = st.build(0,len(arr)-1)\n",
    "\n",
    "        begin = 0\n",
    "        end = 0\n",
    "        while end<len(arr):\n",
    "            #print(mp)\n",
    "            if arr[end][0]-arr[begin][0]<=t:\n",
    "                # end到目前为止还是满足t范围内的\n",
    "                idx = arr[end][1]\n",
    "                '''if mp[idx]>0:\n",
    "                    #print(end,mp)\n",
    "                    return True'''\n",
    "                #print(\"find: \",idx)\n",
    "                if st.findNode(idx,root):\n",
    "                    return True\n",
    "                start = max(idx-k,0)\n",
    "                fin = min(idx+k,len(arr)-1)\n",
    "                #新增的end的idx覆盖了start到fin的范围,如果这部分曾经被覆盖,就表示有过重合\n",
    "                '''for i in range(start,fin+1):\n",
    "                    mp[i] += 1'''\n",
    "                #print(\"add: \",start,fin)\n",
    "                st.addNode(start,fin,root)\n",
    "                end += 1\n",
    "            else:\n",
    "                idx = arr[begin][1]\n",
    "                start = max(idx-k,0)\n",
    "                fin = min(idx+k,len(arr)-1)\n",
    "                '''for i in range(start,fin+1):\n",
    "                    mp[i] -= 1'''\n",
    "                #print(\"del: \",start,fin)\n",
    "                st.delNode(start,fin,root)\n",
    "                begin += 1\n",
    "        #print(mp)\n",
    "        return False\n",
    "\n",
    "class SegTreeNode:\n",
    "    def __init__(self,start,end,weight):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.weight = weight\n",
    "\n",
    "class SegTree:\n",
    "    def build(self,start,end):\n",
    "        return SegTreeNode(start,end,0)\n",
    "\n",
    "    def addNode(self,start,end,root):\n",
    "        #print(\"add: \",start,end,root.start,root.end)\n",
    "        if root.start==start and root.end==end:\n",
    "            root.weight += 1\n",
    "            return \n",
    "        mid = (root.start+root.end)//2\n",
    "        if end<=mid:\n",
    "            #往左加\n",
    "            if root.left==None:\n",
    "                root.left = SegTreeNode(root.start,mid,0)\n",
    "            self.addNode(start,end,root.left)\n",
    "        elif start>mid:\n",
    "            #往右加\n",
    "            if root.right==None:\n",
    "                root.right = SegTreeNode(mid+1,root.end,0)\n",
    "            self.addNode(start,end,root.right)\n",
    "        else:\n",
    "            if root.left==None:\n",
    "                root.left = SegTreeNode(root.start,mid,0)\n",
    "            if root.right==None:\n",
    "                root.right = SegTreeNode(mid+1,root.end,0)\n",
    "            self.addNode(start,mid,root.left)\n",
    "            self.addNode(mid+1,end,root.right)\n",
    "\n",
    "    def delNode(self,start,end,root):\n",
    "        if root.start==start and root.end==end:\n",
    "            root.weight -= 1\n",
    "            return\n",
    "        mid = (root.start+root.end)//2\n",
    "        if end<=mid:\n",
    "            #往左\n",
    "            self.delNode(start,end,root.left)\n",
    "        elif start>mid:\n",
    "            #往右\n",
    "            self.delNode(start,end,root.right)\n",
    "        else:\n",
    "            self.delNode(start,mid,root.left)\n",
    "            self.delNode(mid+1,end,root.right)\n",
    "\n",
    "    def findNode(self,pos,root):\n",
    "        '''if root!=None:\n",
    "            print(\"find!! \",pos,root.start,root.end,root.weight)\n",
    "        else:\n",
    "            print(\"find None \",pos)'''\n",
    "        if root==None:\n",
    "            return False\n",
    "        if root.weight>=1:\n",
    "            return True\n",
    "        if root.start==pos and root.end==pos:\n",
    "            return root.weight>=1\n",
    "        mid = (root.start+root.end)//2\n",
    "        if pos<=mid:\n",
    "            return self.findNode(pos,root.left)\n",
    "        else:\n",
    "            return self.findNode(pos,root.right)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        head = 0\n",
    "        tail = head+indexDiff\n",
    "\n",
    "        buffer = nums[head : tail+1]\n",
    "        buffer.sort()\n",
    "\n",
    "        diffList = [buffer[i]-buffer[i-1] for i in range(1, len(buffer))]\n",
    "\n",
    "        if min(diffList)<=valueDiff:\n",
    "            return True\n",
    "\n",
    "        while True:\n",
    "\n",
    "            head += 1\n",
    "            tail += 1\n",
    "\n",
    "            if tail > len(nums)-1:\n",
    "                return False\n",
    "\n",
    "            removeIndex = self._binarySearch(buffer, nums[head-1])\n",
    "            buffer.pop(removeIndex)\n",
    "\n",
    "            insertIndex = self._binarySearch(buffer, nums[tail])\n",
    "\n",
    "            if insertIndex != 0 and abs(nums[tail] - buffer[insertIndex-1])<=valueDiff:\n",
    "                return True\n",
    "\n",
    "            if insertIndex != len(buffer) and abs(nums[tail] - buffer[insertIndex]) <= valueDiff:\n",
    "                return True\n",
    "\n",
    "            buffer.insert(insertIndex, nums[tail])\n",
    "\n",
    "    def _binarySearch(self, nums, val):\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "\n",
    "        while left <= right:\n",
    "            middle = (left+right) // 2\n",
    "\n",
    "            if val < nums[middle]:\n",
    "                right = middle-1\n",
    "            elif val > nums[middle]:\n",
    "                left = middle+1\n",
    "            else:\n",
    "                return middle\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 桶排序\r\n",
    "class Solution:\r\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\r\n",
    "        if valueDiff < 0 or indexDiff < 0:\r\n",
    "            return False\r\n",
    "        all_buckets = {}\r\n",
    "        bucket_size = valueDiff + 1 # 桶的大小设成t+1更加方便\r\n",
    "        for i in range(len(nums)):\r\n",
    "            bucket_num = nums[i] // bucket_size # 放入哪个桶            \r\n",
    "            if bucket_num in all_buckets: # 桶中已经有元素了\r\n",
    "                return True            \r\n",
    "            all_buckets[bucket_num] = nums[i]   # 把nums[i]放入桶中            \r\n",
    "            if (bucket_num - 1) in all_buckets and \\\r\n",
    "            abs(all_buckets[bucket_num - 1] - nums[i]) \\\r\n",
    "                <= valueDiff: # 检查前一个桶\r\n",
    "                return True            \r\n",
    "            if (bucket_num + 1) in all_buckets and \\\r\n",
    "                abs(all_buckets[bucket_num + 1] - nums[i]) \\\r\n",
    "                    <= valueDiff: # 检查后一个桶\r\n",
    "                return True            \r\n",
    "            # 如果不构成返回条件，那么当i >= k 的时候就要删除旧桶了，\r\n",
    "            # 以维持桶中的元素索引跟下一个i+1索引只差不超过k\r\n",
    "            if i >= indexDiff:\r\n",
    "                all_buckets.pop(nums[i-indexDiff]//bucket_size)                \r\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        # 桶的方法\n",
    "        bucket_dict = dict()\n",
    "        for i in range(len(nums)):\n",
    "            num = nums[i]//(valueDiff+1)\n",
    "            if num in bucket_dict:\n",
    "                return True\n",
    "            bucket_dict[num] = nums[i]\n",
    "            if num-1 in bucket_dict and abs(bucket_dict[num]-bucket_dict[num-1])<=valueDiff:\n",
    "                return True\n",
    "            if num+1 in bucket_dict and abs(bucket_dict[num+1]-bucket_dict[num])<=valueDiff:\n",
    "                return True\n",
    "            # 前面可以直接return True是因为下面把所有大于k的桶都pop掉了\n",
    "            if i>=indexDiff:\n",
    "                bucket_dict.pop(nums[i-indexDiff]//(valueDiff+1))\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        if indexDiff == 0:\n",
    "            return False\n",
    "        window = SortedList([nums[0]])\n",
    "        for i in range(1, len(nums)):\n",
    "            if i > indexDiff:\n",
    "                window.remove(nums[i - indexDiff - 1])\n",
    "            idx = bisect.bisect(window, nums[i])\n",
    "            if (idx - 1 >= 0 and abs(window[idx - 1] - nums[i]) <= valueDiff) or (idx < len(window) and abs(window[idx] - nums[i]) <= valueDiff):\n",
    "                return True\n",
    "            window.add(nums[i])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, indexDiff: int, valueDiff: int) -> bool:\n",
    "        window = SortedList()\n",
    "        l = 0\n",
    "        lens = len(nums)\n",
    "        for r in range(lens):\n",
    "            if window:\n",
    "                ind1 = window.bisect_left(nums[r] - valueDiff)\n",
    "                ind2 = window.bisect_right(nums[r] + valueDiff) - 1\n",
    "\n",
    "                if -1 < ind1 < len(window) and nums[r] >= window[ind1] >= nums[r] - valueDiff:\n",
    "                    return True\n",
    "\n",
    "                if -1 < ind2 < len(window) and nums[r] <= window[ind2] <= nums[r] + valueDiff:\n",
    "                    return True\n",
    "\n",
    "            if r - l == indexDiff:\n",
    "                window.remove(nums[l])\n",
    "                l += 1\n",
    "            window.add(nums[r])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        sl = SortedList()\n",
    "        for i,num in enumerate(nums):\n",
    "            sl.add((num,i))\n",
    "            if i-k>0:\n",
    "                sl.remove((nums[i-k-1],i-k-1))\n",
    "            idx = sl.bisect_left((num,i))\n",
    "            if idx==0 and len(sl)==1:\n",
    "                continue\n",
    "            elif 0<idx<len(sl)-1 and (sl[idx+1][0]-num<=t or num-sl[idx-1][0]<=t):\n",
    "                return True\n",
    "            elif idx==0 and sl[1][0]-num<=t:\n",
    "                return True\n",
    "            elif idx==len(sl)-1 and num-sl[idx-1][0]<=t:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        d = {}\n",
    "        w = valueDiff+1\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            x = num//w\n",
    "            if x in d:\n",
    "                return True\n",
    "            elif x-1 in d and abs(num-d[x-1])<w:\n",
    "                return True\n",
    "            elif x+1 in d and abs(num-d[x+1])<w:\n",
    "                return True\n",
    "\n",
    "            d[x] = num\n",
    "            if i>=indexDiff:\n",
    "                del d[nums[i-indexDiff]//w]\n",
    "\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        #对所有数字//t+1 可以把数字装进不同的桶里 且桶里面的数字满足abs(x-y) <= t\n",
    "        #对数组进行遍历，从i到k时，如果有桶里有俩数，很明显满足\n",
    "        #超过k的时候，就需要把i-k的数从桶里删除，因为不再考虑他们了\n",
    "        all_buckets = {}\n",
    "        bucket_size = t+1\n",
    "        for i in range(len(nums)):\n",
    "            bucket_num = nums[i] // bucket_size # 放入哪个桶\n",
    "            \n",
    "            if bucket_num in all_buckets:       # 桶中已经有元素了\n",
    "                return True\n",
    "            \n",
    "            all_buckets[bucket_num] = nums[i]   # 把nums[i]放入桶中\n",
    "            \n",
    "            if (bucket_num - 1) in all_buckets and abs(all_buckets[bucket_num - 1] - nums[i]) <= t: # 检查前一个桶\n",
    "                return True\n",
    "            \n",
    "            if (bucket_num + 1) in all_buckets and abs(all_buckets[bucket_num + 1] - nums[i]) <= t: # 检查后一个桶\n",
    "                return True\n",
    "            \n",
    "            # 如果不构成返回条件，那么当i >= k 的时候就要删除旧桶了，以维持桶中的元素索引跟下一个i+1索引只差不超过k\n",
    "            if i >= k:\n",
    "                all_buckets.pop(nums[i-k]//bucket_size)\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "\n",
    "        ans = False\n",
    "        rs = []\n",
    "        tables = {}\n",
    "\n",
    "        value = valueDiff\n",
    "\n",
    "        if valueDiff==0:\n",
    "            value = 1\n",
    "                \n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            #print(tables,rs)\n",
    "            if len(rs)>indexDiff:\n",
    "                tables.pop(rs.pop())\n",
    "            k = nums[i] // value\n",
    "            \n",
    "            if k in tables:\n",
    "                ans = True\n",
    "                break\n",
    "            else:\n",
    "                rs.insert(0, k)\n",
    "                tables[k] = nums[i]\n",
    "\n",
    "                pre  = k - 1\n",
    "                nex =  k + 1\n",
    "                if pre in tables:\n",
    "                    if abs(nums[i] - tables[pre]) <= valueDiff:\n",
    "                        ans = True\n",
    "                        break\n",
    "                if nex in tables:\n",
    "                    if abs(nums[i] - tables[nex]) <= valueDiff:\n",
    "                        ans = True\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        ln,lw=len(nums),indexDiff\n",
    "        w0=[nums[0]]                \n",
    "        left=0\n",
    "        for n in nums[1:]:\n",
    "            pos = bisect_left(w0,n)\n",
    "            w0.insert(pos,n)\n",
    "            if (pos and (w0[pos]-w0[pos-1])<=valueDiff) or (pos<len(w0)-1 and (w0[pos+1]-w0[pos])<=valueDiff): return True\n",
    "            if len(w0) > lw: \n",
    "                w0.pop(bisect_left(w0,nums[left]))\n",
    "                left += 1\n",
    "        return False    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        n=len(nums)\n",
    "        if n<=1:\n",
    "            return False\n",
    "        s=set()#定义窗口\n",
    "        for i in range(n):\n",
    "            if valueDiff==0:\n",
    "                #值之差为0,看窗口内是否有重复出现的元素，有返回true\n",
    "                if nums[i] in s:\n",
    "                    return True\n",
    "            else:\n",
    "                for j in s:\n",
    "                #遍历窗口元素，判断是否有绝对值之差小于valueDiff\n",
    "                    if abs(j-nums[i])<=valueDiff:\n",
    "                        return True\n",
    "            s.add(nums[i])#集合中添加元素\n",
    "            if len(s)>indexDiff:\n",
    "                s.remove(nums[i-indexDiff])#保持窗口的长度为indexDiff\n",
    "        return False\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], index_diff: int, value_diff: int) -> bool:\n",
    "        from sortedcontainers import SortedSet\n",
    "        # num_set 维护滑动窗口 [i - index_diff, i) 内的所有数\n",
    "        num_set: SortedSet = SortedSet()\n",
    "        for i, num in enumerate(nums):\n",
    "            # 如果滑动窗口内存在一个数 target 与 num 的差不超过 value_diff ，\n",
    "            # 即 num - value_diff <= target <= num + value_diff ，则满足题意\n",
    "            target: Optional[int] = next(num_set.irange(num - value_diff, num + value_diff), None)\n",
    "            if target is not None:\n",
    "                return True\n",
    "\n",
    "            # 将当前数 num 纳入滑动窗口中\n",
    "            num_set.add(num)\n",
    "            # 将左边界的数移除滑动窗口\n",
    "            if i >= index_diff:\n",
    "                num_set.remove(nums[i - index_diff])\n",
    "\n",
    "        # 在循环中没有返回，则所有数都不满足题意\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        from sortedcontainers import SortedSet\n",
    "        l = r = 0\n",
    "        setA =  SortedSet()\n",
    "        while(r<len(nums)):\n",
    "            while (r-l > indexDiff):\n",
    "                setA.remove(nums[l])\n",
    "                l += 1\n",
    "            index = bisect.bisect_left(setA, nums[r] - valueDiff)\n",
    "           \n",
    "            print(index)\n",
    "            if setA and index>=0 and index <len(setA) and abs(setA[index]-nums[r]) <= valueDiff:\n",
    "                \n",
    "                return True\n",
    "            setA.add(nums[r])\n",
    "            r += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        n = len(nums)\n",
    "        nums_indexes = []\n",
    "        for i in range(n):\n",
    "            nums_indexes.append((nums[i], i))\n",
    "        # key is num,按照数的大小进行排序\n",
    "        # 排序能够解决两个数之间差距的问题，存储下标能解决下标差距问题\n",
    "        nums_indexes.sort(key=lambda x: x[0]) \n",
    "\n",
    "        for i in range(n):\n",
    "            num1 = nums_indexes[i]\n",
    "            for j in range(i + 1, n):\n",
    "                num2 = nums_indexes[j]\n",
    "                # the loop to be end\n",
    "                # 停止的是内层的循环，说明a[0]的情况已经到此为止了\n",
    "                # 因为已经对num进行了排序，后面差值肯定是递增的\n",
    "                if num2[0] - num1[0] > t:     \n",
    "                    break\n",
    "                # abs(a[0] - b[0]) <= t, abs(a[1] - b[1]) <= k\n",
    "                if abs(num2[1] - num1[1]) <= k:   \n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.height = 0\n",
    "        self.number = 0\n",
    "\n",
    "    \n",
    "class avlTree:\n",
    "    def __init__(self, nums=[]):\n",
    "        self.root = None\n",
    "        for i in nums:\n",
    "            self.add(i)\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(list(self.__iter__()))\n",
    "\n",
    "    def __repr__(self):\n",
    "        return repr(list(self.__iter__()))\n",
    "\n",
    "    def __contains__(self, val):\n",
    "        node = self.root\n",
    "        while node:\n",
    "            if val < node.val:\n",
    "                node = node.left\n",
    "            elif val > node.val:\n",
    "                node = node.right\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def __iter__(self):\n",
    "        stack = []\n",
    "        cur = self.root\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stack.pop()\n",
    "            yield cur.val\n",
    "            cur = cur.right\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.number(self.root)\n",
    "\n",
    "    def __getitem__(self, x):\n",
    "        node = self.root\n",
    "        if x < 0:\n",
    "            x = self.number(node)\n",
    "        if (not 0 <= x < self.number(node)):\n",
    "            raise IndexError(\"IndexError: avlTree index out of range\")\n",
    "        while x != self.number(node.left):\n",
    "            if x < self.number(node.left):\n",
    "                node = node.left\n",
    "            elif x > self.number(node.left):\n",
    "                x, node = x-self.number(node.left)-1, node.right\n",
    "        return node.val        \n",
    "        \n",
    "    def height(self, node):\n",
    "        if node is None:\n",
    "            return -1\n",
    "        else:\n",
    "            return node.height\n",
    "\n",
    "    def number(self, node):\n",
    "        if node is None:\n",
    "            return 0\n",
    "        else:\n",
    "            return node.number\n",
    "\n",
    "    def singleLeftRotate(self, node):\n",
    "        k1 = node.left\n",
    "        node.left = k1.right\n",
    "        k1.right = node\n",
    "        node.height = max(self.height(node.right), self.height(node.left)) + 1\n",
    "        node.number = self.number(node.left) + self.number(node.right) + 1\n",
    "        k1.height = max(self.height(k1.left), node.height) + 1\n",
    "        k1.number = self.number(k1.left) + self.number(k1.left) + 1\n",
    "        return k1\n",
    "\n",
    "    def singleRightRotate(self, node):\n",
    "        k1 = node.right\n",
    "        node.right = k1.left\n",
    "        k1.left = node\n",
    "        node.height = max(self.height(node.right), self.height(node.left)) + 1\n",
    "        node.number = self.number(node.left) + self.number(node.right) + 1\n",
    "        k1.height = max(self.height(k1.right), node.height) + 1\n",
    "        k1.number = self.number(k1.left) + self.number(k1.right) + 1\n",
    "        return k1\n",
    "\n",
    "    def doubleRightRotate(self, node):\n",
    "        node.right = self.singleLeftRotate(node.right)\n",
    "        return self.singleRightRotate(node)\n",
    "\n",
    "    def doubleLeftRotate(self, node):\n",
    "        node.left = self.singleRightRotate(node.left)\n",
    "        return self.singleLeftRotate(node)\n",
    "    \n",
    "    def add(self, key):\n",
    "            \n",
    "        def dfs(key, node):\n",
    "            if node is None:\n",
    "                node = TreeNode(key)\n",
    "            elif key <= node.val:\n",
    "                node.left = dfs(key, node.left)\n",
    "                if (self.height(node.left) - self.height(node.right)) == 2:\n",
    "                    if key < node.left.val:\n",
    "                        node = self.singleLeftRotate(node)\n",
    "                    else:\n",
    "                        node = self.doubleLeftRotate(node)\n",
    "            else:\n",
    "                node.right = dfs(key, node.right)\n",
    "                if (self.height(node.right) - self.height(node.left)) == 2:\n",
    "                    if key > node.right.val:\n",
    "                        node = self.singleRightRotate(node)\n",
    "                    else:\n",
    "                        node = self.doubleRightRotate(node)\n",
    "            node.height = max(self.height(node.right), self.height(node.left)) + 1\n",
    "            node.number = self.number(node.left) + self.number(node.right) + 1\n",
    "            return node\n",
    "\n",
    "        self.root = dfs(key, self.root)\n",
    "    \n",
    "    def remove(self, key):\n",
    "            \n",
    "        def dfs(key, node):\n",
    "            if node is None:\n",
    "                raise ValueError(\"avlTree.remove(x): x not in avlTree\")\n",
    "            elif key < node.val:\n",
    "                node.left = dfs(key, node.left)\n",
    "                if (self.height(node.right) - self.height(node.left)) == 2:\n",
    "                    if self.height(node.right.right) >= self.height(node.right.left):\n",
    "                        node = self.singleRightRotate(node)\n",
    "                    else:\n",
    "                        node = self.doubleRightRotate(node)\n",
    "                node.height = max(self.height(node.left), self.height(node.right)) + 1\n",
    "                node.number = self.number(node.left) + self.number(node.right) + 1\n",
    "            elif key > node.val:\n",
    "                node.right = dfs(key, node.right)\n",
    "                if (self.height(node.left) - self.height(node.right)) == 2:\n",
    "                    if self.height(node.left.left) >= self.height(node.left.right):\n",
    "                        node = self.singleLeftRotate(node)\n",
    "                    else:\n",
    "                        node = self.doubleLeftRotate(node)\n",
    "                node.height = max(self.height(node.left), self.height(node.right)) + 1\n",
    "                node.number = self.number(node.left) + self.number(node.right) + 1\n",
    "            elif node.left and node.right:\n",
    "                if node.left.height <= node.right.height:\n",
    "                    minNode = node.right\n",
    "                    while minNode.left:\n",
    "                        minNode = minNode.left\n",
    "                    node.val = minNode.val\n",
    "                    node.right = dfs(node.val, node.right)\n",
    "                else:\n",
    "                    maxNode = node.left\n",
    "                    while maxNode.right:\n",
    "                        maxNode = maxNode.right\n",
    "                    node.val = maxNode.val\n",
    "                    node.left = dfs(node.val, node.left)\n",
    "                node.height = max(self.height(node.left), self.height(node.right)) + 1\n",
    "                node.number = self.number(node.left) + self.number(node.right) + 1\n",
    "            else:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    node = node.left\n",
    "            return node\n",
    "\n",
    "        self.root = dfs(key, self.root)\n",
    "\n",
    "    def index(self, val):\n",
    "        node = self.root\n",
    "        res = 10**9\n",
    "        index = 0\n",
    "        while node:\n",
    "            if val < node.val:\n",
    "                node = node.left\n",
    "            elif val > node.val:\n",
    "                index += self.number(node.left)+1\n",
    "                node = node.right\n",
    "            else:\n",
    "                res = min(res, index+self.number(node.left))\n",
    "                node = node.left                \n",
    "        if res == 10**9:\n",
    "            raise ValueError(f\"{val} is not in avlTree\")\n",
    "        return res\n",
    "\n",
    "    def clear(self):\n",
    "        self.root = None\n",
    " \n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        window = avlTree()\n",
    "        for i in range(len(nums)):\n",
    "            if i > k:\n",
    "                window.remove(nums[i - 1 - k])\n",
    "            window.add(nums[i])\n",
    "            idx = window.index(nums[i])\n",
    "            if idx > 0 and abs(window[idx] - window[idx-1]) <= t:\n",
    "                return True\n",
    "            if idx < len(window) - 1 and abs(window[idx+1] - window[idx]) <= t:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "      n=len(nums)\n",
    "      if n<=1:\n",
    "        return False\n",
    "      s=set()\n",
    "      for i in range(n):\n",
    "        if valueDiff==0:\n",
    "          if nums[i] in s:\n",
    "            return True\n",
    "        else:\n",
    "          for j in s:\n",
    "            if abs(j-nums[i])<=valueDiff:\n",
    "              return True\n",
    "        s.add(nums[i])\n",
    "        if len(s)>indexDiff:\n",
    "          s.remove(nums[i-indexDiff])\n",
    "      return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        from sortedcontainers import SortedSet\n",
    "        st = SortedSet()\n",
    "        left, right = 0, 0\n",
    "        res = 0\n",
    "        while right < len(nums):\n",
    "            if right - left > k:\n",
    "                st.remove(nums[left])\n",
    "                left += 1\n",
    "            index = bisect.bisect_left(st, nums[right] - t)\n",
    "            if st and index >= 0 and index < len(st) and abs(st[index] - nums[right]) <= t:\n",
    "                return True\n",
    "            st.add(nums[right])\n",
    "            right += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        ls = [[nums[i], i] for i in range(len(nums))]\n",
    "        ls.sort(key=lambda x: x[0])\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                if ls[j][0] - ls[i][0] > t:\n",
    "                    break\n",
    "                if abs(ls[j][1] - ls[i][1]) <= k:\n",
    "                    return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        s = []\n",
    "        for i, v in enumerate(nums):\n",
    "            s.append((v, i))\n",
    "        s.sort()\n",
    "        print(s)\n",
    "        for i in range(len(s) - 1):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[j][0] - s[i][0] <= valueDiff and abs(s[j][1] - s[i][1]) <= indexDiff:\n",
    "                    # print(s[j], s[i])\n",
    "                    return True\n",
    "                if s[j][0] - s[i][0] > valueDiff:\n",
    "                    break\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        hashmap = {}\n",
    "        if valueDiff == 0:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] not in hashmap:\n",
    "                    hashmap[nums[i]] = i\n",
    "                else:\n",
    "                    if i - hashmap[nums[i]] <= indexDiff:\n",
    "                        return True\n",
    "                    else:\n",
    "                        hashmap[nums[i]] = i\n",
    "            return False \n",
    "        for i in range(len(nums)):\n",
    "            ind = nums[i] // valueDiff\n",
    "            if ind in hashmap:\n",
    "                return True\n",
    "            if ind-1 in hashmap:\n",
    "                if abs(hashmap[ind-1] - nums[i]) <= valueDiff:\n",
    "                    return True\n",
    "            if ind+1 in hashmap:\n",
    "                if abs(hashmap[ind+1] - nums[i]) <= valueDiff:\n",
    "                    return True\n",
    "            hashmap[ind] = nums[i]\n",
    "            if i - indexDiff >= 0:\n",
    "                ind = nums[i - indexDiff] // valueDiff\n",
    "                del hashmap[ind]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        n = len(nums)\n",
    "        bucket = {}\n",
    "        for i in range(n):\n",
    "            # 计算当前元素所在的桶编号\n",
    "            idx = nums[i] // (t+1)\n",
    "            if idx in bucket:\n",
    "                return True\n",
    "            if idx-1 in bucket and abs(nums[i]-bucket[idx-1]) <= t:\n",
    "                return True\n",
    "            if idx+1 in bucket and abs(nums[i]-bucket[idx+1]) <= t:\n",
    "                return True\n",
    "            bucket[idx] = nums[i]\n",
    "            # 删除下标范围不符合要求的桶\n",
    "            if i >= k:\n",
    "                del_idx = nums[i-k] // (t+1)\n",
    "                del bucket[del_idx]\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        all_buckets = {} #创建所有桶\n",
    "        buckets_size = valueDiff + 1 # 桶按能被 valueDiff +1 整除分类，也就是数值的差小于valueDiff\n",
    "        for i in range(len(nums)): # 遍历所有元素\n",
    "            buckets_num = nums[i] // buckets_size # 计算该元素位于哪一个桶中\n",
    "\n",
    "            if buckets_num in all_buckets: # 如果该桶存在(也就是有元素)，那么就返回True\n",
    "                return True\n",
    "\n",
    "            all_buckets[buckets_num] = nums[i] # 不存在则创建该桶\n",
    "\n",
    "            # 检查位于前一个桶中，并在该桶中元素差值小于valueDiff的数是否存在\n",
    "            if buckets_num - 1 in all_buckets and abs(all_buckets[buckets_num -1] - nums[i]) <= valueDiff:\n",
    "                return True\n",
    "            # 检查位于后一个桶中，并在该桶中元素差值小于valueDiff的数是否存在\n",
    "            if buckets_num + 1 in all_buckets and abs(all_buckets[buckets_num +1] - nums[i]) <= valueDiff:\n",
    "                return True\n",
    "            # 如果不构成True时，应该将i-indexDiff之前的元素从桶中移除\n",
    "            if i >= indexDiff:\n",
    "                all_buckets.pop(nums[i-indexDiff]//buckets_size)\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        buckets = dict()\n",
    "        for i, n in enumerate(nums):\n",
    "            bucket_id = n // (valueDiff + 1)\n",
    "            if bucket_id in buckets and i - buckets[bucket_id] <= indexDiff:\n",
    "                return True\n",
    "            elif bucket_id-1 in buckets and i - buckets[bucket_id-1] <= indexDiff and \\\n",
    "                n - nums[buckets[bucket_id-1]] <= valueDiff:\n",
    "                return True\n",
    "            elif bucket_id+1 in buckets and i - buckets[bucket_id+1] <= indexDiff and \\\n",
    "                nums[buckets[bucket_id+1]] - n <= valueDiff:\n",
    "                return True\n",
    "            buckets[bucket_id] = i\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        index = [i for i in range(len(nums))]\n",
    "        z = list(zip(nums,index))\n",
    "        z.sort(key = lambda x:x[0])\n",
    "        for i in range(len(z)):\n",
    "            for j in range(i+1,len(z)):\n",
    "                if abs(z[i][0]-z[j][0])<=valueDiff and abs(z[i][1]-z[j][1])<=indexDiff:\n",
    "                    return True\n",
    "                if abs(z[i][0]-z[j][0])>valueDiff:\n",
    "                    break\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        t=valueDiff\n",
    "        k=indexDiff\n",
    "\n",
    "        nums2=[]\n",
    "        for i in range(len(nums)):\n",
    "            nums2.append([nums[i],i])\n",
    "        nums2.sort()\n",
    "        \n",
    "        #newnums,newid=[],[]\n",
    "        #for item in nums2:\n",
    "        #    newnums.append(item[0]),newid.append(item[1])\n",
    "        #nums2=nums.copy()\n",
    "        #newnums,newid=paixu(nums)\n",
    "        \n",
    "        def panduan(nums2,k,t):\n",
    "            for i in range(len(nums2)):\n",
    "                j=i+1\n",
    "                right=t+nums2[i][0]\n",
    "                while j<len(nums2) and nums2[j][0]<=right:\n",
    "                    if abs(nums2[i][1]-nums2[j][1])<=k:\n",
    "                        return True\n",
    "                    j=j+1\n",
    "            return False        \n",
    "        return panduan(nums2,k,t)            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        t={}\n",
    "        tt={}\n",
    "        for i in range(min(indexDiff+1,len(nums))):\n",
    "            k=nums[i]//(valueDiff+1)\n",
    "            if k in t:return True\n",
    "            if k+1 in t and abs(nums[t[k+1]]-nums[i])<=valueDiff:return True\n",
    "            if k-1 in t and abs(nums[t[k-1]]-nums[i])<=valueDiff:return True\n",
    "            t[k],tt[i]=i,k\n",
    "        for i in range(indexDiff+1,len(nums)):\n",
    "            t.pop(tt[i-indexDiff-1])\n",
    "            k=nums[i]//(valueDiff+1)\n",
    "            if k in t:return True\n",
    "            if k+1 in t and abs(nums[t[k+1]]-nums[i])<=valueDiff:return True\n",
    "            if k-1 in t and abs(nums[t[k-1]]-nums[i])<=valueDiff:return True\n",
    "            t[k],tt[i]=i,k\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        # n = len(nums)\n",
    "        k = [[i,j] for i, j in enumerate(nums)]\n",
    "        k.sort(key= lambda x:x[1])\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if k[j][1] - k[i][1] > valueDiff: break\n",
    "                elif abs(k[j][0] - k[i][0]) <= indexDiff:return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        record = {}\n",
    "        diff = valueDiff + 1\n",
    "        for i in range(len(nums)):\n",
    "            k = nums[i] // diff\n",
    "            if k in record:\n",
    "                if i - record[k] <= indexDiff:\n",
    "                    return True\n",
    "            record[k] = i\n",
    "            if k + 1 in record:\n",
    "                if i - record[k+1] <= indexDiff and nums[record[k+1]] - nums[i] <= valueDiff:\n",
    "                    return True\n",
    "            if k - 1 in record:\n",
    "                if i - record[k-1] <= indexDiff and nums[i] - nums[record[k-1]] <= valueDiff:\n",
    "                    return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
